Notations infixée, préfixée, polonaise et postfixée

Les notations infixée (ou infixe), préfixée (ou préfixe) et postfixée (ou postfixe) sont des formes d'écritures d'expressions algébriques qui se distinguent par la position relative qu'y prennent les opérateurs et leurs opérandes. Un opérateur est écrit avant ses opérandes en notation préfixée, entre ses opérandes en notation infixée et après ses opérandes en notation postfixée.

La notation infixée n'a de sens que pour les opérateurs prenant exactement deux opérandes. C'est la notation la plus courante des opérateurs binaires en mathématiques. Les notations préfixée et postfixée permettent de se passer de parenthèses, conduisant à une notation plus compacte. Mais se passer de parenthèse suppose que l'on connaît la signature (autrement dit l'arité de tous les opérateurs) et que cette arité est un attribut des opérateurs qui ne peut pas être modifiable. La signature sert à analyser les expressions lors de leur évaluation.

La notation préfixée fut proposée en 1924 par le mathématicien polonais Jan Łukasiewicz, c'est pourquoi elle est également appelée notation de Łukasiewicz, ou notation polonaise. Par analogie, la notation postfixée est appelée notation polonaise inverse. Ces deux notations (préfixée et postfixée) permettent de se passer de parenthèses dans le cas d'opérateurs d'arité fixée et connue et s'accordent à une évaluation naturelle de l'expression.

Présentation

L'expression qui ajoute les nombres 1 et 2 s'écrit, en notation préfixée, + 1 2. Dans les expressions préfixées, les opérateurs précèdent toujours leurs opérandes qui peuvent être eux-mêmes des expressions non-triviales. Par exemple, l'expression qui serait écrite en notation infixée classique :

(5 − 6) × 7

est écrite en notation préfixée :

× (− 5 6) 7

On notera que comme on connait l'arité des opérateurs, les parenthèses sont inutiles et l'expression précédente peut être simplifiée en :

× − 5 6 7

L'évaluation du produit × est activée quand ses deux opérandes ont été évaluées (à savoir, 5 − 6 et 7). Plus généralement l'évaluation d'un opérateur d'arité n est activée après que ses n opérandes ont été évaluées.

Supposons que l'on ait, de plus, une fonction $f$ d'arité 3 et trois variables $x$, $y$ et $z$. L'expression infixée $f(x,f(x+y,z,z),f(x,x,y))$ s'écrira de façon préfixée, sans parenthèses, $fxf+xyzzfxxy$. Le premier $f$ a trois arguments qui sont $x$, $f+xyzz$ et $fxxy$. Dans l'expression $f+xyzz$, on voit que $f$ a trois arguments $+xy$, puis $z$, puis $z$. L'utilisation d'une pile permet, même à un humain, d'analyser et d'évaluer ces expressions.

Exemples

Notation préfixée

Calcul des propositions de Łukasiewicz

En calcul des propositions, Łukasiewicz introduisait ^{[réf. nécessaire]}:

$N$ pour le « non » $\lnot$ ;

$K$ pour le « et » $\land$ ;

$A$ pour le « ou » $\lor$ ;

$C$ pour l'implication $\to$ ;

$E$ pour l'équivalence $\leftrightarrow$.

Par exemple :

$CpAqm$ correspond à la notation infixée $p\to (q\lor m)$

$ACpqm$ correspond à la notation infixée $(p\to q)\lor m$.

Lisp

Les langages de programmation Lisp et Scheme utilisent une notation préfixée avec parenthèses, pour autoriser les opérateurs ayant un nombre d'opérandes variable. Des parenthèses encadrent un opérateur et ses opérandes.

L'expression usuelle 3 * (4 + 5 + 6) se note dans cette famille de langages (* 3 (+ 4 5 6)).

L'expression est interprétée en remplaçant successivement une expression entre parenthèses par le résultat de l'opérateur écrit à gauche agissant sur les valeurs des opérandes écrites à sa suite :

(* 3 (+ 4 5 6)) ⇒ (* 3 15) ⇒ 45.

Notation postfixée

Les langages de programmation Forth, PostScript et le langage RPL des calculatrices HP utilisent une notation postfixée pouvant se passer de parenthèses, les opérateurs ayant un nombre fixe d'opérandes (l'addition et la multiplication ont deux opérandes, l'inverse et la racine carrée n'en ont qu'une). L'expression 3 * ((4 + 5) + 6) s'écrit alors 3 4 5 add 6 add mul, tandis que l'expression (4 + (5 + 6)) * 3 s'écrit 4 5 6 add add 3 mul. Lorsque l'interprète rencontre un opérande, il l'empile dans une pile, pour pouvoir le dépiler de la pile plus tard. Lorsqu'il rencontre un opérateur binaire, il dépile deux opérandes, applique l'opérateur sur ceux-ci et empile le résultat. La pile aura donc successivement le contenu suivant (le signe ⇒ sépare les étapes qui se succèdent dans le temps):

(3) ⇒ (3 4) ⇒ (3 4 5) ⇒ add ⇒ (3 9) ⇒ (3 9 6) ⇒ add ⇒ (3 15) ⇒ mul ⇒ (45).

Analogue en langage naturel

La notation préfixée de l'expression 3 * (4 + 5 + 6) est analogue à l'expression en langage naturel : « le produit de 3 et de la somme de 4, 5 et 6 ». L'analogue en langage naturel de la notation postfixée 4 5 add 6 add 3 mul serait : « prendre 4 et 5 et les additionner, prendre le résultat et 6 et les additionner puis prendre cette somme et 3 et les multiplier ».

Langage formel des notations postfixées

Les notations postfixées (comme les notations infixées) forment un langage formel dont les mots sont composés des opérateurs et des variables. On peut caractériser parmi tous les mots sur cet alphabet ceux qui correspondent à une notation préfixée. Cela se fait grâce à la notion de valence.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Polish notation » (voir la liste des auteurs).

Articles connexes

• Langage de Łukasiewicz
• Arborescence
• Compilateur